1546C - AquaMoon and Strange Sort - CodeForces Solution

            #include <bits/stdc++.h>
            using namespace std;
            //using sorting comparitive function to sort vector pairs in asceding order by the second element.
            struct sort_pred {
                bool operator()(const pair<int,int> &left, const pair<int,int> &right) {
                        return left.second>right.second;
                }
            };
            struct custom_hash {
                static uint64_t splitmix64(uint64_t x) {
                    x += 0x9e3779b97f4a7c15;
                    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                    return x ^ (x >> 31);
                }
         
                size_t operator()(uint64_t x) const {
                    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                    return splitmix64(x + FIXED_RANDOM);
                }
            };
            int getint () {
            	bool minus = false;
            	int result = 0;
            	char ch;
            	ch = getchar();
            	while (true) {
            		if (ch == '-') break;
            		if (ch >= '0' && ch <= '9') break;
            		ch = getchar();
            	}
            	if (ch == '-') minus = true; else result = ch-'0';
            	while (true) {
            		ch = getchar();
            		if (ch < '0' || ch > '9') break;
            		result = result*10 + (ch - '0');
            	}
            	if (minus)
            		return -result;
            	else
            		return result;
            }
            bool cmp(vector<long long> x,vector<long long> y){
                return x<y;
            }
            bool ispalindrome(vector<long long> x){
                long long N=x.size();
                for(long long i=0;i<N;i++){
                    if(x[i]!=x[N-i-1]){
                        return false;
                    }
                }
                return true;
            }
            const int MAXN = 4e5+1;
            vector<bool> prime(MAXN,1);
            void sieve(){
            	prime[0] = prime[1] = false;
            	for (int i = 2; i <= MAXN; i++) {
            		if (prime[i] && (long long)i * i <= MAXN) {
            			for (int j = i * i; j <= MAXN; j += i)
            				prime[j] = false;
            		}
            	}
            }
            bool isprime(long long x){
                for(int i=2;i<=sqrt(x);i++){
                    if(x%i==0){
                        return false;
                    }
                }
                return true;
            }
        	const double PIE = 3.14159265358979323846;
     
             const long long MOD =1e9+7;
             void solver(){
                long long N;
                cin>>N;
                vector<long long> values(N);
                map<long long,long long> odd;
                map<long long,long long> even;
                map<long long,long long> neweven;
                map<long long,long long> newodd;
                for(int i=0;i<N;i++){
                    cin>>values[i];
                    if(i%2==0){
                        even[values[i]]++;
                    }else{
                        odd[values[i]]++;
                    }
                }
                sort(values.begin(),values.end());
                for(int i=0;i<N;i++){
                    if(i%2==0){
                        neweven[values[i]]++;
                    }else{
                        newodd[values[i]]++;
                    }
                }
                for(auto& c:even){
                    if(even[c.first]!=neweven[c.first]){
                        cout<<"NO"<<"\n";
                        return;
                    }
                }
                
                for(auto& c:odd){
                    if(odd[c.first]!=newodd[c.first]){
                        cout<<"NO"<<"\n";
                        return;
                    }
                }
                cout<<"YES"<<"\n";
                return;


                

                
     
            }
             
            int main()
            {
                #define int long long
            	int N;
            	N=getint();
            	while(N--){
            		solver();
            	}
             
            }